#include <bits/stdc++.h>

using namespace std;

const long long MAXN = 1'000'001;

class Solution
{
    int min_prime[MAXN];

    void sieve()
    {
        for (int i = 2; i < MAXN; ++i)
        {
            min_prime[i] = i;
        }
        min_prime[0] = min_prime[1] = -1;
        for (int i = 2; (long long)i * i < MAXN; ++i)
        {
            if (min_prime[i] == i)
            {
                for (long long j = i * i; j < MAXN; j += i)
                {
                    if (min_prime[j] == j)
                    {
                        min_prime[j] = i;
                    }
                }
            }
        }
    }

    vector<int> get_prime_factors(int n)
    {
        vector<int> factors;
        if (n <= 1)
            return factors;
        while (n > 1)
        {
            int p = min_prime[n];
            factors.push_back(p);
            while (n % p == 0)
            {
                n /= p;
            }
        }
        return factors;
    }

public:
    int minJumps(vector<int> &nums)
    {
        sieve();
        int n = nums.size();
        if (n <= 1)
        {
            return 0;
        }

        vector<unordered_set<int>> adj(n);
        unordered_map<int, vector<int>> pos;

        for (int i = 0; i < n; ++i)
        {
            vector<int> factors = get_prime_factors(nums[i]);
            for (int p : factors)
            {
                pos[p].push_back(i);
            }
        }

        for (int i = 0; i < n; ++i)
        {
            if (i > 0)
                adj[i].insert(i - 1);
            if (i < n - 1)
                adj[i].insert(i + 1);

            if (min_prime[nums[i]] == nums[i] && nums[i] > 1)
            {
                int p = nums[i];
                if (pos.count(p))
                {
                    for (int j : pos[p])
                    {
                        if (i != j)
                        {
                            adj[j].insert(i);
                        }
                    }
                }
            }
        }

        queue<pair<int, int>> q;
        q.push({n - 1, 0});
        vector<bool> visited(n, false);
        visited[n - 1] = true;

        while (!q.empty())
        {
            auto [u, dist] = q.front();
            q.pop();

            if (u == 0)
            {
                return dist;
            }

            for (int v : adj[u])
            {
                if (!visited[v])
                {
                    visited[v] = true;
                    q.push({v, dist + 1});
                }
            }
        }

        return -1;
    }
};
int main()
{

    // system("pause");
    return 0;
}
